using System;
using System.Collections.Generic;
namespace GraphSpace
{
	public class Dial<T> : IPQ<T> where T : DijkstraKnoten, new()
	{
		private List<int>[] buckets;
		private Dictionary<int, T> elements;
		private int c;
		
		public Dial()
		{
			this.c = 0;
		}
		
		public void init(int C)
		{
			this.c = C;
			buckets = new List<int>[c + 2];
			for (int i = 0; i < c + 2; i++)
				buckets[i] = new List<int> ();
			elements = new Dictionary<int, T> ();
		}
		
		public Dial (int C)
		{
			this.c = C;
			buckets = new List<int>[c + 2];
			for (int i = 0; i < c + 2; i++)
				buckets[i] = new List<int> ();
			elements = new Dictionary<int, T>();
		}
			
		public T extractHead()
		{
			// ersten nicht leeren Bucket suchen und erstes Element zurückgeben
			for(int i=0; i< c+2; i++)
			{	
				if(buckets[i].Count>0)
				{
					return elements[buckets[i][0]];
				}
		    }
		
			return default(T);
		}
		
		public bool insert(T item)
		{	
			try
			{
				// Element in Hilfstrukturen und Bucket für unendlich eintragen
				elements.Add(item.Id, item);				// Dictionary Id -> Dial_Knoten
				buckets[c+1].Add(item.Id);					// im Unendlich-Bucket an letzter Stelle einfügen
				item.setBucket(c+1);						// Zeiger auf Bucket setzen
				item.setHeapPos(buckets[c+1].Count-1);		// Zeiger auf Position im Bucket setzen
				return true;
			}
			catch(Exception e)
			{
				Console.WriteLine("Dial::insert : "+e.ToString());
				return false;
			}
		}
		
		public bool decreaseKey (int id, double key)
		{
			try
			{
				// Zuerst im alten Bucket entfernen und Zeiger der übrigen Elemente im Bucket aktuallisieren
				buckets[elements[id].getBucket ()].RemoveAt (elements[id].getHeapPos ());
				for (int i = (elements[id].getHeapPos ()); i < buckets[elements[id].getBucket ()].Count; i++)
				{
					int position = elements[buckets[elements[id].getBucket ()][i]].getHeapPos ()-1;
					elements[buckets[elements[id].getBucket ()][i]].setHeapPos (position);	
				}
				// Anschliessend den Knoten im neunen Bucket einfügen und seine Zeiger anpassen
				int d = ((int)key)%(c+1);
				buckets[d].Add(id);
				elements[id].setBucket (d);
				elements[id].setHeapPos(buckets[d].Count-1);
				
				return true;
			}
			catch(Exception e)
			{
				Console.WriteLine("Fehler in Dial::decreaseKey("+id+", "+key+")"+e.ToString());
				return false;
			}
		}
		
		public bool isEmpty()
		{
			for(int i=0; i<c+1; i++)
				if(buckets[i].Count>0)
					return false;
			return true;				
		}
		
		public void show()
		{
			// Alle normalen Buckets
			for(int i = 0; i< c+1; i++)
			{
				Console.WriteLine("\t"+i+". Bucket");
				foreach(int j in buckets[i])
					Console.WriteLine("\t\t"+elements[j].ToString());
			}
			// unendlicher Bucket
			Console.WriteLine("\tunendliches Bucket");
			foreach(int j in buckets[c+1])
				Console.WriteLine("\t\t"+elements[j].ToString());
		}
	}
	
	
	public class BiDial<T> : IPQ<T> where T : BiDijkstraKnoten, new()
	{
		private List<int>[] buckets;
		private Dictionary<int, T> elements;
		private int c;
		
		public BiDial()
		{
			this.c = 0;
		}
		
		public void init(int C)
		{
			this.c = C;
			buckets = new List<int>[c + 2];
			for (int i = 0; i < c + 2; i++)
				buckets[i] = new List<int> ();
			elements = new Dictionary<int, T> ();
		}
		
		public BiDial (int C)
		{
			this.c = C;
			buckets = new List<int>[c + 2];
			for (int i = 0; i < c + 2; i++)
				buckets[i] = new List<int> ();
			elements = new Dictionary<int, T>();
		}
			
		public T extractHead()
		{
			// ersten nicht leeren Bucket suchen und erstes Element zurückgeben
			for(int i=0; i< c+2; i++)
			{	
				if(buckets[i].Count>0)
				{
					return elements[buckets[i][0]];
				}
		    }
		
			return default(T);
		}
		
		public bool insert(T item)
		{	
			try
			{
				// Element in Hilfstrukturen und Bucket für unendlich eintragen
				elements.Add(item.Id, item);				// Dictionary Id -> Dial_Knoten
				buckets[c+1].Add(item.Id);					// im Unendlich-Bucket an letzter Stelle einfügen
				item.setBucket(c+1);						// Zeiger auf Bucket setzen
				item.setHeapPos(buckets[c+1].Count-1);		// Zeiger auf Position im Bucket setzen
				return true;
			}
			catch(Exception e)
			{
				Console.WriteLine("Dial::insert : "+e.ToString());
				return false;
			}
		}
		
		public bool decreaseKey (int id, double key)
		{
			try
			{
				// Zuerst im alten Bucket entfernen und Zeiger der übrigen Elemente im Bucket aktuallisieren
				buckets[elements[id].getBucket ()].RemoveAt (elements[id].getHeapPos ());
				for (int i = (elements[id].getHeapPos ()); i < buckets[elements[id].getBucket ()].Count; i++)
				{
					int position = elements[buckets[elements[id].getBucket ()][i]].getHeapPos ()-1;
					elements[buckets[elements[id].getBucket ()][i]].setHeapPos (position);	
				}
				// Anschliessend den Knoten im neunen Bucket einfügen und seine Zeiger anpassen
				int d = ((int)key)%(c+1);
				buckets[d].Add(id);
				elements[id].setBucket (d);
				elements[id].setHeapPos(buckets[d].Count-1);
				
				return true;
			}
			catch(Exception e)
			{
				Console.WriteLine("Fehler in Dial::decreaseKey("+id+", "+key+")"+e.ToString());
				return false;
			}
		}
		
		public bool isEmpty()
		{
			for(int i=0; i<c+1; i++)
				if(buckets[i].Count>0)
					return false;
			return true;				
		}
		
		public void show()
		{
			// Alle normalen Buckets
			for(int i = 0; i< c+1; i++)
			{
				Console.WriteLine("\t"+i+". Bucket");
				foreach(int j in buckets[i])
					Console.WriteLine("\t\t"+elements[j].ToString());
			}
			// unendlicher Bucket
			Console.WriteLine("\tunendliches Bucket");
			foreach(int j in buckets[c+1])
				Console.WriteLine("\t\t"+elements[j].ToString());
		}
	}
}

